package Classic150;

public class 最大子数组和 {
    /*
        动态规划，dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和
        根据状态的定义，由于 nums[i] 一定会被选取，并且以 nums[i] 结尾的连续子数组与以 nums[i - 1] 结尾的连续子数组只相差一个元素 nums[i]
        以下对于dp[i]来看：
        如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组
        如果 dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]
        dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]
        注意这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去
        这个问题的输出是把所有的 dp[0]、dp[1]、……、dp[n - 1] 都看一遍，取最大值
     */
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE, sum = 0;
        for (int num : nums) {
            if (sum > 0) sum += num;
            else sum = num;
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }
}
